水管铺设问题

现有10个村庄，要在村庄之间铺设自来水管道，求可以使各村庄连通起来的管道长度最短的方案。下表为各个村庄之间的距离，0表示不连通。

NetworkX求解过程

第一步：准备数据

输入数据，引入相应的库

import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
import pandas as pd
data = {1: {1: 0, 2: 5, 3: 6, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 9, 10: 0},
 2: {1: 5, 2: 0, 3: 1, 4: 2, 5: 12, 6: 0, 7: 5, 8: 0, 9: 0, 10: 2},
 3: {1: 6, 2: 1, 3: 0, 4: 6, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
 4: {1: 0, 2: 2, 3: 6, 4: 0, 5: 8, 6: 0, 7: 4, 8: 0, 9: 0, 10: 3},
 5: {1: 0, 2: 12, 3: 0, 4: 8, 5: 0, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0},
 6: {1: 0, 2: 0, 3: 7, 4: 0, 5: 0, 6: 0, 7: 5, 8: 0, 9: 7, 10: 0},
 7: {1: 0, 2: 5, 3: 0, 4: 4, 5: 0, 6: 5, 7: 0, 8: 10, 9: 0, 10: 0},
 8: {1: 0, 2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 10, 8: 0, 9: 0, 10: 0},
 9: {1: 9, 2: 0, 3: 0, 4: 0, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
 10: {1: 0, 2: 2, 3: 0, 4: 3, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0}}
pipeline = pd.DataFrame(data) # 将数据转为DataFrame格式

第二步：生成图

NetworkX有多种从数据转换为图的方式，这里采用的是从DataFrame数据格式进行转换；另一个比较常见的方式是通过邻接矩阵，直接通过nx.Graph(A)生成，其中A为邻接矩阵。

G = nx.from_pandas_adjacency(pipeline) # 根据DataFrame格式数据生成图

第三步：生成最小生成树

G_tree = nx.minimum_spanning_tree(G,weight='weight') # 计算赋权图的最小生成树

这里一定要注意需要在nx.minimum_spanning_tree中加入参数weight='weight'，否则默认计算的是不加权的最小生成树，与预期不符。

第四步： 输出结果

print(G_tree.edges) # 显示最小生成树的边

通过边我们便可以获得该问题的解答方案：

[(10, 2), (9, 6), (8, 5), (7, 4), (7, 6), (5, 4), (4, 2), (3, 2), (2, 1)]

进一步可视化可以绘制出网络图

pos = nx.layout.circular_layout(G) # 设置图的排布格式，这里用的是环状排布
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8)  # 绘制无向图
labels = nx.get_edge_attributes(G,'weight') # 获取赋权图的标签数据
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels, font_color='m') # 显示边的权值
nx.draw_networkx_edges(G,pos,edgelist=G_tree.edges,edge_color='orange',width=4)  # 设置指定边的颜色

完整代码

import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
import pandas as pd
data = {1: {1: 0, 2: 5, 3: 6, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 9, 10: 0},
 2: {1: 5, 2: 0, 3: 1, 4: 2, 5: 12, 6: 0, 7: 5, 8: 0, 9: 0, 10: 2},
 3: {1: 6, 2: 1, 3: 0, 4: 6, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
 4: {1: 0, 2: 2, 3: 6, 4: 0, 5: 8, 6: 0, 7: 4, 8: 0, 9: 0, 10: 3},
 5: {1: 0, 2: 12, 3: 0, 4: 8, 5: 0, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0},
 6: {1: 0, 2: 0, 3: 7, 4: 0, 5: 0, 6: 0, 7: 5, 8: 0, 9: 7, 10: 0},
 7: {1: 0, 2: 5, 3: 0, 4: 4, 5: 0, 6: 5, 7: 0, 8: 10, 9: 0, 10: 0},
 8: {1: 0, 2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 10, 8: 0, 9: 0, 10: 0},
 9: {1: 9, 2: 0, 3: 0, 4: 0, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
 10: {1: 0, 2: 2, 3: 0, 4: 3, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0}}
pipeline = pd.DataFrame(data) # 将数据转为DataFrame格式
G = nx.from_pandas_adjacency(pipeline) # 根据DataFrame格式数据生成图
G_tree = nx.minimum_spanning_tree(G,weight='weight') # 计算赋权图的最小生成树
print(G_tree.edges)
pos = nx.layout.circular_layout(G) # 设置图的排布格式，这里用的是环状排布
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8)  # 绘制无向图
labels = nx.get_edge_attributes(G,'weight') # 获取赋权图的标签数据
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels, font_color='m') # 显示边的权值
nx.draw_networkx_edges(G,pos,edgelist=G_tree.edges,edge_color='orange',width=4)  # 设置指定边的颜色

---

import matplotlib.pyplot as plt
%matplotlib inline
import networkx as nx
import pandas as pd
data = {1: {1: 0, 2: 5, 3: 6, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 9, 10: 0},
 2: {1: 5, 2: 0, 3: 1, 4: 2, 5: 12, 6: 0, 7: 5, 8: 0, 9: 0, 10: 2},
 3: {1: 6, 2: 1, 3: 0, 4: 6, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
 4: {1: 0, 2: 2, 3: 6, 4: 0, 5: 8, 6: 0, 7: 4, 8: 0, 9: 0, 10: 3},
 5: {1: 0, 2: 12, 3: 0, 4: 8, 5: 0, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0},
 6: {1: 0, 2: 0, 3: 7, 4: 0, 5: 0, 6: 0, 7: 5, 8: 0, 9: 7, 10: 0},
 7: {1: 0, 2: 5, 3: 0, 4: 4, 5: 0, 6: 5, 7: 0, 8: 10, 9: 0, 10: 0},
 8: {1: 0, 2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 10, 8: 0, 9: 0, 10: 0},
 9: {1: 9, 2: 0, 3: 0, 4: 0, 5: 0, 6: 7, 7: 0, 8: 0, 9: 0, 10: 0},
 10: {1: 0, 2: 2, 3: 0, 4: 3, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0}}
pipeline = pd.DataFrame(data) # 将数据转为DataFrame格式
G = nx.from_pandas_adjacency(pipeline) # 根据DataFrame格式数据生成图
G_tree = nx.minimum_spanning_tree(G,weight='weight') # 计算赋权图的最小生成树
print(G_tree.edges) # 显示最小生成树的边
pos = nx.layout.circular_layout(G) # 设置图的排布格式，这里用的是环状排布
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8)  # 绘制无向图
labels = nx.get_edge_attributes(G,'weight') # 获取赋权图的标签数据
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels, font_color='m') # 显示边的权值
nx.draw_networkx_edges(G,pos,edgelist=G_tree.edges,edge_color='orange',width=4)  # 设置指定边的颜色
plt.savefig('images/net0202.png')

[(10, 2), (9, 6), (8, 5), (7, 4), (7, 6), (5, 4), (4, 2), (3, 2), (2, 1)]